package com.study.algorithm.base.tree;

import com.study.algorithm.base.tree.model.TreeNode;
import org.apache.commons.lang3.RandomUtils;


import java.util.*;

/**
 * 二叉树
 *
 * @author wanghuilong
 * @version 1.0
 * @date 2022/6/21 6:06 下午
 */
public class BinaryTreeTest {

    /**
     * 通过最简单的方法实现，观察其中的规律(可以通过绘图梳理流程)
     * 树的分析过程：
     *  1、定义(根节点:最顶部的节点 叶节点:没有子节点的节点 子树:包含当前节点和所有子节点)
     *  2、基本遍历方式 ，其中的步骤和特点（树的递归序）  递归是使用JVM中的栈，非递归就是自己压栈
     *  3、在递归序的基础上，可以加工成三种顺序： 加工(这些操作，都是通过基本的递归顺序加工得到的)
     *      先序(对于所有子树都是先头、左、右)、中序(对于所有子树都是先左、头、右)、后序(对于所有子树都是先左、右、头)
     *      先序(对于所有子树都是先头、左、右)：将根节点压栈，弹出就打印，再将子节点压入栈中，先压右再压左
     *      中序(对于所有子树都是先左、头、右)：每棵子树，整棵树左边界(所有左节点)进栈，依次弹出的过程中打印，再对弹出的节点右树做同样整棵树左边界(所有左节点)进栈
     *      后序(对于所有子树都是先左、右、头)：将先序改为(头，右，左)即将打印的节点，依次压入另一个栈中，再依次弹出打印就变成了后序-> 左、右、头
     *
     *  二叉树的宽度优先遍历(求二叉树的宽度)  用队列，队列先进先出，弹出的节点打印，之后以先左节点再右节点的方式压入队列
     *  二叉树的深度度优先遍历(求二叉树的高度) 先序遍历
     *  优先：先打印的深度/宽度方向上的节点，深度:优先每棵子树的根节点 宽度:整个树的每一层的节点
     * @param args
     */

    public static void main(String[] args) {
        TreeNode treeNode = getCompleteBinaryTree(3);
        printFirst(treeNode);
        System.out.println();
        printFirstNoRecursion(treeNode);
        System.out.println();
        preOrderUnRecursion(treeNode);
        printMiddleNoRecursion2(treeNode);
        System.out.println();
        inOrderUnRecursion(treeNode);
        widthFirstTraversal(treeNode);
        getTreeWidth(treeNode);
        getTreeWidthWithOutHashMap(treeNode);
        System.out.println("isSearchBinaryTree:"+isSearchBinaryTree(treeNode));
        TreeNode searchBinaryTree = getSearchBinaryTree(3);
        System.out.println("searchBinaryTree isSearchBinaryTree:"+isSearchBinaryTree(searchBinaryTree));
        System.out.println("isSearchBinaryTreeNoRecursion:"+isSearchBinaryTreeNoRecursion(treeNode));
        System.out.println("searchBinaryTree isSearchBinaryTreeNoRecursion:"+isSearchBinaryTreeNoRecursion(searchBinaryTree));
    }

    /**
     * is complete binary tree
     * For every sub tree,if the root node only has one sub node ,it must be the left node，or
     *
     * @param head
     * @return
     */
    public static boolean isCompleteBinaryTree(TreeNode head) {
        if(null == head) {
            return false;
        }
        return true;
    }



    /**
     *  is a search binary tree
     *  search binary tree: For every sub tree, its root node's value bigger than its left sub node's value
     *  , and smaller than its right sub node's value
     *  By inorder traverse the tree to get the list of values , the list's order must be ascending
     * @param head
     */
    public static boolean isSearchBinaryTree(TreeNode head) {
        if(null == head) {
            return false;
        }
        int value = head.getValue();
        TreeNode leftNode = head.getLeftNode();
        if(null != leftNode && value < leftNode.getValue()) {
            return false;
        }
        TreeNode rightNode = head.getRightNode();
        if(null != rightNode && value > rightNode.getValue()) {
            return false;
        }
        return (null != leftNode?isSearchBinaryTree(leftNode):true) && (null != rightNode?isSearchBinaryTree(rightNode):true);
    }

    /**
     *  is a search binary tree
     *  search binary tree: For every sub tree, its root node's value bigger than its left sub node's value
     *  , and smaller than its right sub node's value
     *  By inorder traverse the tree to get the list of values , the list's order must be ascending
     * @param head
     */
    public static boolean isSearchBinaryTreeNoRecursion(TreeNode head) {
        if(null == head) {
            return false;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.add(head);
        while(!stack.isEmpty()) {
            head = stack.pop();
            int value = head.getValue();
            TreeNode leftNode = head.getLeftNode();
            if(null != leftNode && value < leftNode.getValue()) {
                return false;
            }
            TreeNode rightNode = head.getRightNode();
            if(null != rightNode && value > rightNode.getValue()) {
                return false;
            }
            if(null != rightNode) {
                stack.push(rightNode);
            }
            if(null != leftNode) {
                stack.push(leftNode);
            }
        }

        return true;
    }


    public static TreeNode getSearchBinaryTree(int height) {
        int nodeNum = 0;
        for (int i = 0; i < height; i++) {
            nodeNum += Math.pow(2,i);
        }
        List<TreeNode> list = new ArrayList();
        for (int i = 1; i <= nodeNum; i++) {
            TreeNode treeNode = new TreeNode();
            treeNode.setValue(RandomUtils.nextInt(1,10000));
            list.add(treeNode);
        }
        TreeNode head = null;
        for (TreeNode treeNode:list) {
            if(head == null) {
                head = treeNode;
                continue;
            }
            TreeNode lastNode = null;
            TreeNode node = head;
            while (null != node) {
                lastNode = node;
                if(node.getValue()  > treeNode.getValue()) {
                    node = node.getLeftNode();
                }else {
                    node = node.getRightNode();
                }
            }
            if(lastNode.getValue()  >  treeNode.getValue()) {
                lastNode.setLeftNode(treeNode);
            }else {
                lastNode.setRightNode(treeNode);
            }
        }
        return head;
    }

    public static void widthFirstTraversal(TreeNode head) {
        System.out.print("width first traversal print: ");
        if(null == head) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            System.out.print(" "+head.getValue()+" ");
            if(null != head.getLeftNode()) {
                queue.offer(head.getLeftNode());
            }
            if(null != head.getRightNode()) {
                queue.offer(head.getRightNode());
            }
        }
        System.out.println();
    }

    public static void getTreeWidth(TreeNode head) {
        System.out.print("tree width: ");
        if(null == head) {
            return ;
        }
        Queue<TreeNode> queue = new LinkedList();
        Map<TreeNode,Integer> treeNodeLevelMap = new HashMap<>();
        int maxWidth = 0;
        int level = 1;
        int nowWidth = 0;
        treeNodeLevelMap.put(head,level);
        queue.offer(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            Integer treeNodeLevel = treeNodeLevelMap.get(head);
            if(treeNodeLevel == level) {
                nowWidth++;
            }else {
                maxWidth = Math.max(maxWidth,nowWidth);
                level = treeNodeLevel;
                nowWidth = 1;
            }
            if(null != head.getLeftNode()) {
                queue.offer(head.getLeftNode());
                treeNodeLevelMap.put(head.getLeftNode(),level+1);
            }
            if(null != head.getRightNode()) {
                queue.offer(head.getRightNode());
                treeNodeLevelMap.put(head.getRightNode(),level+1);
            }
        }
        maxWidth = Math.max(maxWidth,nowWidth);
        System.out.print(maxWidth);
        System.out.println();
    }

    /**
     *
     * @param head
     */
    public static void getTreeWidthWithOutHashMap(TreeNode head) {
        System.out.print("tree width withOut hashMap : ");
        if (null == head) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(head);
        TreeNode currentEndNode = null;
        TreeNode nextLevelEndNode = null;
        int maxWidth = 1;
        int currentLevelWidth = 0;
        while (!queue.isEmpty()){
            head = queue.poll();
            if(null == currentEndNode) {
                currentEndNode = head;
            }
            currentLevelWidth++;
            if(null != head.getLeftNode()) {
                queue.offer(head.getLeftNode());
                nextLevelEndNode = head.getLeftNode();
            }
            if(null != head.getRightNode()) {
                queue.offer(head.getRightNode());
                nextLevelEndNode = head.getRightNode();
            }
            if(head == currentEndNode) {
                currentEndNode = nextLevelEndNode;
                nextLevelEndNode = null;
                maxWidth = Math.max(currentLevelWidth,maxWidth);
                currentLevelWidth = 0;
            }
        }
        maxWidth = Math.max(maxWidth,currentLevelWidth);
        System.out.print(maxWidth);
        System.out.println();
    }

    /**
     * 获取完全二叉tree
     * @param high
     * @return
     */
    private static TreeNode getCompleteBinaryTree(int high) {
        int nodeNum = 0;
        for (int i = 0; i < high; i++) {
            nodeNum += Math.pow(2,i);
        }
        List<TreeNode> list = new ArrayList();
        for (int i = 1; i <= nodeNum; i++) {
            TreeNode treeNode = new TreeNode();
            treeNode.setValue(i);
            list.add(treeNode);
        }
        TreeNode head = null;
        for (int i = 0; i < list.size(); i++) {
            TreeNode treeNode = list.get(i);
            if(i == 0) {
                head = treeNode;
            }
            //左子节点的下标 = 2*i + 1
            int leftIndex = 2*i + 1;
            if(leftIndex >= 0 && leftIndex < list.size()) {
                treeNode.setLeftNode(list.get(leftIndex));
            }
            //右子节点的下标 = 2*i + 2
            int rightIndex = 2*i + 2;
            if(rightIndex >= 0 && rightIndex < list.size()) {
                treeNode.setRightNode(list.get(rightIndex));
            }
            //父节点的下标 = (i - 1)/2
            int parentIndex = (i - 1)/2;
            if(parentIndex >= 0 && parentIndex < list.size()) {
                TreeNode parentNode = list.get(parentIndex);
                if(null != parentNode)  {
                  int parentLeftIndex =  2*parentIndex + 1;
                  //判断是父节点的左子节点
                  if(i == parentLeftIndex) {
                      parentNode.setLeftNode(treeNode);
                  }else {
                      parentNode.setRightNode(treeNode);
                  }
                }
            }
        }
        return head;
    }

    /**
     * 打印树
     * @param head
     */
    public static void print(TreeNode head) {

    }


    private static int getTreeHigh(TreeNode head) {
        if(null == head) {
            return 0;
        }
        int len = 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        TreeNode node = head.getLeftNode();
        if(null == node) {
            node = head.getRightNode();
        }
        while (null != node && node != head) {
            stack.push(node);
            node = node.getLeftNode();
            while(null != node && !stack.contains(node)) {
                stack.push(node);
                node = node.getLeftNode();
            }
            if(stack.size() > len) {
                len = stack.size();
            }
            node = node.getRightNode();
            while (null == node) {
                TreeNode lastNode = stack.pop();
                node = lastNode.getRightNode();
            }
            while(null != node && !stack.contains(node)) {
                stack.push(node);
                node = node.getRightNode();
            }
            if(stack.size() > len) {
                len = stack.size();
            }
            stack.pop();
            node = stack.pop();
        }
        return len;
    }

    /**
     * middle sequence traverse the binary tree
     * @param head
     */
    private static void printMiddle(TreeNode head) {
        if(null == head) {
            return;
        }
        printMiddle(head.getLeftNode());
        System.out.print(" "+head.getValue()+" ");
        printMiddle(head.getRightNode());
    }

    /**
     * first sequence traverse the binary tree
     * @param head
     */
    private static void printFirst(TreeNode head) {
        if(null == head) {
            return;
        }
        System.out.print(" "+head.getValue()+" ");
        printFirst(head.getLeftNode());
        printFirst(head.getRightNode());
    }

    /**
     * last sequence traverse the binary tree
     * @param head
     */
    private static void printLast(TreeNode head) {
        if(null == head) {
            return;
        }
        printLast(head.getLeftNode());
        printLast(head.getRightNode());
        System.out.print(" "+head.getValue()+" ");
    }

    /**
     * No recursion first sequence traverse the binary tree
     * @return
     */
    private static void printFirstNoRecursion(TreeNode head) {
        if(null == head) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        TreeNode node = stack.pop();
        while (null != node) {
            System.out.print(" " + node.getValue() + " ");
            TreeNode rightNode = node.getRightNode();
            if(null != rightNode) {
                stack.push(rightNode);
            }
            TreeNode leftNode = node.getLeftNode();
            if(null != leftNode) {
                stack.push(leftNode);
            }
            if(!stack.isEmpty()) {
                node = stack.pop();
            }else {
                node = null;
            }
        }
    }

    /**
     * No recursion middle sequence traverse the binary tree
     * @return
     */
    private static void  printMiddleNoRecursion(TreeNode head) {
        if(null == head) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        TreeNode leftNode = null;
        TreeNode rightNode = null;
        while (!stack.isEmpty() || null != rightNode || null != leftNode) {
            TreeNode node = stack.pop();
            while (null != node) {
                stack.push(node);
                node = node.getLeftNode();
            }
            node = stack.pop();
            while (!stack.isEmpty() && null == node.getRightNode()) {
                System.out.print(" "+node.getValue()+" ");
                node = stack.pop();
            }
            System.out.print(" "+node.getValue()+" ");

            node = node.getRightNode();
            while(null != node) {
                stack.push(rightNode);
                node = node.getRightNode();
            }

            node = stack.pop();
            while (!stack.isEmpty()) {
                System.out.print(" "+node.getValue()+" ");
                node = stack.pop();
            }
        }
    }

    /**
     * No recursion middle sequence traverse the binary tree
     * @return
     */
    private static void  printMiddleNoRecursion2(TreeNode head) {
        if(null == head) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        TreeNode leftNode = head.getLeftNode();
        TreeNode rightNode = null;
        //0:左 1:右
        int key = 0;
        while (!stack.isEmpty() || null != leftNode || null != rightNode) {
            if(null != leftNode) {
                stack.push(leftNode);
                leftNode = leftNode.getLeftNode();
                continue;
            }
            if(0 == key) {
                leftNode = stack.pop();
                while (!stack.isEmpty() && null == leftNode.getRightNode()) {
                    System.out.print(" " + leftNode.getValue() + " ");
                    leftNode = stack.pop();
                }
                System.out.print(" " + leftNode.getValue() + " ");
                rightNode = leftNode.getRightNode();
                leftNode = null;
                key = 1;
            }
            if(null != rightNode) {
                stack.push(rightNode);
                rightNode = rightNode.getRightNode();
                continue;
            }
            if(1 == key) {
                rightNode = stack.pop();
                while (!stack.isEmpty() && null == rightNode.getLeftNode()) {
                    System.out.print(" " + rightNode.getValue() + " ");
                    rightNode = stack.pop();
                }
                System.out.print(" " + rightNode.getValue() + " ");
                if(rightNode == head) {
                    leftNode = rightNode.getRightNode();
                }else {
                    leftNode = rightNode.getLeftNode();
                }
                rightNode = null;
                key = 0;
            }
        }
    }

    /**
     * standard answer
     * No recursion inorder traverse the binary tree
     * @return
     */
    public static void inOrderUnRecursion(TreeNode head) {
        System.out.print("inorder no recursion print: ");
        if(null != head) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (!stack.isEmpty() || head != null) {
                if(head != null) {
                    stack.push(head);
                    head = head.getLeftNode();
                }else {
                    head = stack.pop();
                    System.out.print(" " + head.getValue() + " ");
                    head = head.getRightNode();
                }
            }
        }
        System.out.println();
    }

    /**
     * standard answer
     * No recursion preorder traverse the binary tree
     * @return
     */
    public static void preOrderUnRecursion(TreeNode head) {
        System.out.print("preorder no recursion print: ");
        if(null != head) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(" " + head.getValue() + " ");
                if(head.getRightNode() != null) {
                    stack.push(head.getRightNode());
                }
                if(head.getLeftNode() != null) {
                    stack.push(head.getLeftNode());
                }
            }
        }
        System.out.println();
    }
}
